Матч 343, CD Проигрыватель (CDPlayer)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

В только что купленном Вами CD плеере есть n песен. Плеер поддерживает функцию “random”, которая работает по следующему алгоритму:

1. Выбрать произвольную перестановку из n песен;

2. Проиграть n песен согласно выбранной перестановке;

3. Перейти в пункт 1;

Массив songlist содержит набор строк, описывающий последовательность проигрывания песен. Каждая песня кодируется заглавной буквой латинского алфавита. Разные песни кодируются разными буквами. Напрмер, последовательности песен “ABCCAB” и “BCABCA” являются корректными, а “AABBCC” – нет.

Однажды проигрыватель сломался, и он начинает проигрывать песни не с начала перестановки, а с некоторой ее части. Например, он может проиграть последовательность “BBAC”. Новая перестановка песен в ней начинается с 1 позиции. Песня B, стоящая в позиции 0, принадлежит предыдущей перестановке.

По заданному массиву песен songlist необходимо определить наименьший индекс, с которого начинается новая перестановка песен. Если такого индекса не существует, вернуть -1.

Класс: CDPlayer

Метод: int isRandom(vector<string> songlist, int n)

Ограничения: songlist содержит от 1 до 50 строк, содержит от 1 до 50 символов ‘A’ – ‘Z’, 1 £ n £ 26.

Вход. Список песен songlist и целое число n.

Выход. Наименьший индекс массива songlist, с которого начинается новая перестановка песен. Если такого индекса не существует, вернуть -1.

Пример входа

songlist	n
{"BBAC"}	3
{"BACAB", "BCA"}	3
{"AAACBACBACBACBACBACBACB"}	3

Пример выхода

1

2

-1

РЕШЕНИЕ

перебор

Образуем строку песен song, объединив все строки массива songlist. Перебираем все возможные позиции j начала перестановки из n песен (0 £ j < n). Позиция j будет искомой, если:

1. Все песни с нулевой позиции до (j – 1) - ой разные;

2. Все песни с позиции j + n*k до (j + n*k + n – 1) разные для k = 0, 1, 2, … ;

Наименьшая позиция j, удовлетворяющая приведенным условиям, будет искомой. Если такой позиции не существует, то имеющийся список песен является некорректным и следует вернуть -1.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <memory>

using namespace std;

class CDPlayer

{

public:

int isRandom(vector<string> songlist, int n)

{

string song;

int i,j,used[26];

for(i=0;i<songlist.size();i++) song += songlist[i];

for(j=0;j<n;j++)

{

memset(used,0,sizeof(used));

for(i=0;i<j;i++)

{

if (used[song[i]-'A']) break;

used[song[i]-'A'] = 1;

}

if (i < j) continue;

for(;i<song.size();i++)

{

if (i % n == j) memset(used,0,sizeof(used));

if (used[song[i]-'A']) break;

used[song[i]-'A'] = 1;

}

if (i < song.size()) continue;

return j;

}

return -1;

}

};